package net.cloudsun.tree.avl;

import net.cloudsun.tree.binary.BinaryNode;
import net.cloudsun.tree.orderbinary.OrderBinaryNode;

/**
 * @author Ryan
 * @since
 */
public class AVLNode<T extends Comparable<T>> extends OrderBinaryNode<T> {

    public AVLNode(T t) {
        super(t);
    }

    @Override
    public void add(BinaryNode<T> newNode) {
        final AVLNode<T> avlNode = (AVLNode<T>) super.innerAdd((OrderBinaryNode<T>) newNode);
        avlNode.fixToBalance();
    }

    @Override
    public void delete() {
        super.delete();
        this.fixToBalance();
    }

    void fixToBalance() {
        // 往上找直到子树不平衡
        for(AVLNode<T> pointer = this;pointer != null; pointer = (AVLNode<T>) pointer.parent) {
            final int heightDiff = pointer.getLeftHeight() - pointer.getRightHeight();
            if (heightDiff > 1) {
                // LL 或 LR
                final AVLNode<T> left = pointer.getLeft();
                if (left.getLeftHeight() < left.getRightHeight()) {
                    // LR
                    // 先子树RR，再整体LL
                    pointer.lr();
                } else {
                    // LL
                    pointer.ll();
                }
            } else if (heightDiff < -1) {
                // RR 或 RL
                final AVLNode<T> right = pointer.getRight();
                if (right.getLeftHeight() > right.getRightHeight()) {
                    // RL
                    pointer.rl();
                } else {
                    pointer.rr();
                }
            }
            if (heightDiff > 1 || heightDiff < -1) {
                break;
            }
        }
    }

    private int getLeftHeight() {
        if (getLeft() == null) {
            return 0;
        }
        return this.getLeft().height;
    }

    private int getRightHeight() {
        if (getRight() == null) {
            return 0;
        }
        return this.getRight().height;
    }

    @Override
    public AVLNode<T> getLeft() {
        return (AVLNode<T>) super.getLeft();
    }

    @Override
    public AVLNode<T> getRight() {
        return (AVLNode<T>) super.getRight();
    }

    @Override
    public AVLNode<T> getParent() {
        return (AVLNode<T>) super.getParent();
    }

    // 四大旋转

    /**
     * 其实是右旋
     *   3    2
     *  2 -> 1 3
     * 1
     * @return
     */
    private void ll() {
        // 代码有失误，这里创建了新节点

        super.rightRotate();
    }

    /**
     * 其实是左旋
     * 这里代码有失误，不应该创建新的节点
     * 1      2
     *  2 -> 1 3
     *   3
     * @return
     */
    private void rr() {
        super.leftRotate();
    }

    /**
     *    7        3
     *   2    ->  2 7
     *    3
     * @return
     */
    private void lr() {
        this.getLeft().rr();
        this.ll();
    }

    /**
     * 5       6
     *   7 -> 5 7
     *  6
     * @return
     */
    private void rl() {
        this.getRight().ll();
        this.rr();
    }
}
